package com.tgy.programmer_code_interview_guide._02_linkedList;

import com.tgy.leetcode.ListNode;

/**
 * @Author: tgy
 * @Date: 1/28/21 11:06 AM
 */
public class _13_单链表的选择排序 {


    public static ListNode selectSort(ListNode root) {

        ListNode dummyNewNode = new ListNode();
        ListNode tailNode = dummyNewNode;

        ListNode dummyNode = new ListNode();
        dummyNode.next = root;
        ListNode preNode,minPreNode,node;
        int min;

        while (true) {

            node = dummyNode.next;
            if (node == null) {
                break;
            }
            minPreNode = null;
            min = Integer.MAX_VALUE;
            preNode = dummyNode;

            while (node != null) {

                if (node.val < min) {

                    minPreNode = preNode;
                    min = node.val;
                }
                preNode = node;
                node = node.next;
            }

            tailNode.next = minPreNode.next;
            tailNode = minPreNode.next;
            minPreNode.next = minPreNode.next.next;
        }

        return dummyNewNode.next;
    }

    public static void main(String[] args) {

        ListNode root = ListNode.general(new int[]{2, 1, 1,4, 3, 5, 0});
        root = selectSort(root);
        ListNode.printListNode(root);
    }
}
